package interviewusa;

// 这道题做错了
public class SortLinkList {
    public static void main(String[] args) {
        SortLinkList SortLinkList = new SortLinkList();
        ListNode head = new ListNode(4);
        head = SortLinkList.add(head, new ListNode(2));
        head = SortLinkList.add(head, new ListNode(1));
        head = SortLinkList.add(head, new ListNode(3));
        SortLinkList.print(head);
        SortLinkList.print(SortLinkList.sort(head));
    }
    public void print(ListNode head) {

        ListNode cur = head;
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.next;
        }
    }
    public ListNode add(ListNode head, ListNode node) {

        if (head == null) {
            return node;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
        return head;
    }
    public ListNode sort(ListNode head) {

        ListNode i = head;
        ListNode pre = new ListNode(-1);
        ListNode deleteNode;
        ListNode sortedList = null;
        ListNode sortedListPre = new ListNode(-1);
        while (i != null) {
            int min = i.val;
            ListNode j = i;
            deleteNode = i;
            while (j.next != null) {
                if (j.next.val < min) {
                    min = j.next.val;
                    deleteNode = j.next;
                    pre = j;
                }
                j = j.next;
            }
            pre.next = deleteNode.next;
            ListNode listNode = new ListNode(min);
            if (sortedList == null) {
                sortedList = listNode;
            } else {
                sortedListPre.next = listNode;
            }
            sortedListPre = listNode;
            if (i.next == null) {
                listNode.next = head;
            }
            i = i.next;
        }
        return sortedList;
    }
}



}
